public class BinaryTreeTest {
    //孩子表示法实现二叉树
    static class TreeNode {
        //1.建立数据域、左孩子的引用和右孩子的引用
        public char val;
        public TreeNode left;//存储左孩子的引用
        public TreeNode right;//存储右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //开始创建二叉树
    public TreeNode createTree() {
        //2.创建二叉树的结点
        TreeNode treeNodeA = new TreeNode('A');
        TreeNode treeNodeB = new TreeNode('B');
        TreeNode treeNodeC = new TreeNode('C');
        TreeNode treeNodeD = new TreeNode('D');
        TreeNode treeNodeE = new TreeNode('E');
        TreeNode treeNodeF = new TreeNode('F');
        TreeNode treeNodeG = new TreeNode('G');
        TreeNode treeNodeH = new TreeNode('H');

        //3.有左孩子赋值到左边，有右孩子的赋值到右边并确定根节点
        treeNodeA.left = treeNodeB;
        treeNodeB.left = treeNodeD;
        treeNodeB.right = treeNodeE;
        treeNodeE.right = treeNodeH;
        treeNodeA.right = treeNodeC;
        treeNodeC.left = treeNodeF;
        treeNodeC.right = treeNodeG;
        return treeNodeA;//确定根节点
    }

    /*
     * @ 二叉树面试题
     * N0.1 检查两棵树是否相同
     * */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //pheq其中有个等于null就说明不相同
        if (p == null && q != null || p != null && q == null) {
            return false;
        }
        //p和q相同
        if (p == null && q == null) {
            return true;
        }
        //结点的值不相同
        if (p.val != q.val) {
            return false;
        }
        //调用方法继续找p和q的下一个左树和下一个右树
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /*
     * @ 二叉树面试题
     * NO.2 另一棵树的子树
     * */
    public boolean isSubTree(TreeNode root, TreeNode subRoot) {
        //如果root和subRoot为空 - subRoot不是root的子树
        if (root == null || subRoot == null) {
            return false;
        }
        //调用方法判断两棵树是不是相同的
        if (isSameTree(root, subRoot)) {
            return true;//相同说明subRoot是root的子树
        }
        //subRoot是root.left的子树
        if (isSubTree(root.left, subRoot)) {
            return true;
        }
        //subRoot是root.right的子树
        if (isSubTree(root.right, subRoot)) {
            return true;
        }
        //全部遍历未找到返回false
        return false;
    }

    /*
     * @ 二叉树面试题
     * NO.3 对称二叉树
     * */
    public boolean isSymmetric(TreeNode root) {
        //如果root为空则是对称的
        if (root == null) {
            return true;
        }
        //判断root的左树和右树
        return isSymmetricChild(root.left, root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree) {
        //左树和右树一个等于空一个不等于空
        if (leftTree == null && rightTree != null || leftTree != null && rightTree == null) {
            return false;
        }
        //左树和右树等于空
        if (leftTree == null && rightTree == null ) {
            return true;
        }
        //左树的值不等于右树的值
        if (leftTree.val != rightTree.val) {
            //不对称
            return false;
        }
        //走到这说明左和右要么都为空要么都不为空并且左右的值不一样
        //调用方法查找左树和右树
        return isSymmetricChild(leftTree.left, rightTree.right) && isSymmetricChild(leftTree.right, rightTree.left);
    }

    /*
     * @ 二叉树面试题
     * NO.4 翻转二叉树
     * */
    public TreeNode invertTree(TreeNode root) {
        //root为空
        if (root == null) {
            return null;
        }
        //定义一个临时变量 - 交换结点的值
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        //调用方法去翻转左树和右树
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /*
     * @ 二叉树面试题
     * NO.5 平衡二叉树
     * */
    public boolean isBalanced(TreeNode root) {
        //为空
        if (root == null) {
            return true;//为空是平衡的情况
        }
        //不为空的情况
        int leftH = maxdepth(root.left);//求左树的高度
        int rightH = maxdepth(root.right);//求右树的高度
        //左树减右树的绝对值小于2并且调用方法找左边和右边是不是平衡的
        return Math.abs(leftH - rightH) < 2 && isBalanced(root.left) && isBalanced(root.right);
    }

    //求二叉树的高度
    public int maxdepth(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        int leftHeight = maxdepth(root.left);//找左边
        int rightHeight = maxdepth(root.right);//找右边
        //返回左和右的最大高度加1
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    /*
     * @ 二叉树面试题
     * NO.6 二叉书的构建及遍历
     * */
    public static int i = 0;
    public static TreeNode createNode(String str) {
        TreeNode root = null;
        //当前的字符不等于#
        if (str.charAt(i) != '#') {
            //新建一个结点
            root = new TreeNode(str.charAt(i));
            //找字符串的下一个字符
            i++;
            //调用方法找到左边和右边的位置
            root.left = createNode(str);
            root.right = createNode(str);
        }else {
            //如果是字符#则不创建结点
            i++;//找到下一个
        }
        return root;
    }



    public static void main(String[] args) {
        BinaryTreeTest binaryTreeTest = new BinaryTreeTest();
        BinaryTreeTest.TreeNode root = BinaryTreeTest.createNode("ABC##DE#G##F###");
    }
}
